/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <iostream>

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
	treeHeight = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	RC rc;
	rc = pf.open(indexname + ".idx", mode);
    return rc;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	RC rc;
	rc = pf.close();
    return rc;
}

RC BTreeIndex::recursive(int key, RecordId rid, int parentpid, int depth, int currentpid, int& mid, PageId& sibpid, int& needSplit)
{
	RC rc;
	PageId pid;
	int m;
	PageId sp;
	int split;
	BTNonLeafNode temp1;
	temp1.read(0,pf);
	treeHeight = temp1.getTreeHeight();
	if(depth == treeHeight)
	{
		BTLeafNode leaf;
		leaf.read(currentpid,pf);
		if(leaf.insert(key,rid) != 0)
		{
			needSplit = 1;
			PageId lastpid = pf.endPid();
			int siblingkey;
			BTLeafNode sibling;
			PageId temp = leaf.getNextNodePtr();
			leaf.insertAndSplit(key, rid, sibling, siblingkey);
			leaf.setNextNodePtr(lastpid);
			leaf.write(currentpid,pf);
			sibling.setNextNodePtr(temp);
			sibling.write(lastpid,pf);
			mid = siblingkey;
			sibpid = lastpid;
			temp1.read(0,pf);
			rootPid = temp1.getRootPid();
			if(currentpid == rootPid)
			{
				treeHeight = temp1.getTreeHeight();
				treeHeight++;
				temp1.setTreeHeight(treeHeight);
				temp1.write(0,pf);
				BTNonLeafNode R;
				PageId newpage = pf.endPid();
				rootPid = newpage;
				temp1.setRootPid(rootPid);
				temp1.write(0,pf);
				rc = R.initializeRoot(currentpid,mid,sibpid);
				R.write(newpage,pf);
				needSplit = 0;
				return rc;
			}
			return 0;
		}
		else
		{
			needSplit = 0;
			leaf.write(currentpid,pf);
		}
		return 0;
	}
	BTNonLeafNode leafnode;
	leafnode.read(currentpid,pf);
	leafnode.locateChildPtr(key, pid);
	recursive(key,rid,currentpid,depth+1,pid,m,sp,split);
	if(split == 1)
	{
		BTNonLeafNode parent;
		parent.read(currentpid,pf);
		if(parent.insert(m,sp) != 0)
		{
			needSplit = 1;
			PageId siblingpid = pf.endPid();
			BTNonLeafNode sibling;
			int midkey;
			parent.insertAndSplit(m, sp, sibling, midkey);
			parent.write(currentpid,pf);
			sibling.write(siblingpid,pf);
			mid = midkey;
			sibpid = siblingpid;
			temp1.read(0,pf);
			rootPid = temp1.getRootPid();
			if(currentpid == rootPid)
			{
				BTNonLeafNode R;
				PageId newpage = pf.endPid();
				treeHeight = temp1.getTreeHeight();
				treeHeight++;
				temp1.setTreeHeight(treeHeight);
				rootPid = newpage;
				temp1.setRootPid(rootPid);
				temp1.write(0,pf);
				rc = R.initializeRoot(currentpid,mid,sibpid);
				R.write(newpage,pf);
				needSplit = 0;
				return rc;
			}
			return 0;
		}
		else
		{
			needSplit = 0;
			parent.write(currentpid,pf);
		}
		return 0;
	}
	needSplit = 0;
	return 0;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	PageId lastpid = pf.endPid();
	if(lastpid == 0)
	{
		BTNonLeafNode temp;
		rootPid = 0;
		treeHeight = 0;
		temp.setRootPid(rootPid);
		temp.setTreeHeight(treeHeight);
		temp.write(0,pf);
		lastpid = pf.endPid();
	}
	if(lastpid == 1)
	{
		rootPid = 1;
		BTLeafNode leafnode;
		BTNonLeafNode temp;
		temp.read(0,pf);
		temp.setRootPid(rootPid);
		temp.setTreeHeight(treeHeight);
		temp.write(0,pf);
		leafnode.read(rootPid,pf);
		leafnode.insert(key,rid);
		leafnode.setNextNodePtr(RC_END_OF_TREE);
		leafnode.write(rootPid,pf);
	}
	else
	{
		
		int m;
		PageId sp;
		int split;
		BTNonLeafNode temp;
		temp.read(0,pf);
		rootPid = temp.getRootPid();
		recursive(key,rid,-1,0,rootPid,m,sp,split);
	}
    return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,0
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	int depth = 0;
	BTNonLeafNode temp;
	temp.read(0,pf);
	rootPid = temp.getRootPid();
	treeHeight = temp.getTreeHeight();
	BTNonLeafNode node;
	RC rc;
	PageId k;
	node.read(rootPid, pf);
	while(depth != treeHeight)
	{
		depth++;
		if(node.locateChildPtr(searchKey,cursor.pid) == 0)
			node.read(cursor.pid,pf);
		else
		{
			return RC_NO_SUCH_RECORD;
		}
	}
	if(depth == 0)
		cursor.pid = rootPid;
	BTLeafNode leaf;
	leaf.read(cursor.pid,pf);
	rc = leaf.locate(searchKey,cursor.eid);
    return rc;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	BTLeafNode leaf;
	RC rc;
	leaf.read(cursor.pid,pf);
	rc = leaf.readEntry(cursor.eid, key, rid);
	cursor.eid++;
	if(cursor.eid >= leaf.getKeyCount())
	{
		
		PageId nextpage = leaf.getNextNodePtr();
		cursor.pid = nextpage;
		cursor.eid = 0;
		if(leaf.getNextNodePtr() == RC_END_OF_TREE)
			return RC_END_OF_TREE;
	}
    return rc;
}


